#include<vector>
using namespace std;

class Solution {
    vector<vector<int>> dp;
public:
    int uniquePaths(int m, int n) {
        dp.resize(m + 1);
        for (int i = 0; i <= m; i++) {
            dp[i].resize(n + 1, -1);
        }
        return dfs(m, n);
    }
    int dfs(int x, int y) {
        if (dp[x][y] != -1)return dp[x][y];
        if (x < 1 || y < 1) {
            dp[x][y] = 0;
            return 0;
        }
        if (x == 1 && y == 1) {
            dp[x][y] = 1;
            return 1;
        }
        dp[x][y] = dfs(x, y - 1) + dfs(x - 1, y);
        return dp[x][y];
    }
};